Vangin pasianssissa 52 kortin sekoitetusta korttipakasta ladotaan pöydälle 13 ja nämä yhdistetään saman arvoisiksi pinoiksi. Tämän jälkeen loput kortit käydään läpi kolme kerrallaan siten, että vain joka kolmas otetaan huomioon (eli sama asia kun otettaisiin pakasta vain 13 seuraavaa korttia). Jos pakasta nostettu kortti on arvoltaan sama kuin pöydällä oleva pino, niin tämän pinon saa poistaa.
Mikä on todennäköisyys, että pöydälle jää lopuksi k korttia, k=0, 1, 2, ... 13?
Tein tällaisen, missä peliä voi testata (klikkaa pakkaa (vihreä ylä-vasemmalla) pelataksesi kortti/tripletti kerrallaan tai nopeuta peliä ja klikkaa alemmista napeista.
https://prisoners-solitaire--minkkilaukku2.repl.co/
Vangin pasianssin todennäköisyydet
18
198
Vastaukset 18
- Anonyymi
Hankala löytää eksaktia tapaa. Tein simulaation, 100000 ajoa. todennäköisyydet k:lle kortille, k=0,...,13 olivat
2e-05
0.00113
0.00905
0.04398
0.12532
0.22919
0.27041
0.20021
0.09166
0.02523
0.00351
0.00028
1e-05Hmmm.. Itse saan vähän eri tulokset:
P(X=0) = 0.003702
P(X=1) = 0.019696
P(X=2) = 0.057118
P(X=3) = 0.113366
P(X=4) = 0.1673
P(X=5) = 0.192721
P(X=6) = 0.178426
P(X=7) = 0.13303
P(X=8) = 0.078939
P(X=9) = 0.03777
P(X=10) = 0.013507
P(X=11) = 0.00377
P(X=12) = 0.000607
P(X=13) = 0.000048
(Jäikö sinulta yksi pois, kun niitähän pitäisi olla 14?)
Tein simulaation uudestaan kolmella eri kielellä ja koitin aina unohtaa entisen, mutta sehän saattaa olla, että itse minulla tuli sitten kaikissa sama ajatusvirhe. Täältä löytyy tekeleitäni (C ja Python-versiot): https://github.com/minkkilaukku/prisoners-solitaire ja JS on täällä: https://repl.it/@minkkilaukku2/Prisoners-Solitaire
Siellä Python-tiedostossa on myös yritystä laskea tarkasti, laitan ehkä toiseen viestiin niitä pohdelmiani, ettei tästä nyt tule niin pitkä.
Jos tuo tarina, että 5000 kertaa piti vangin koittaa ennen kuin onnistui on totta (tai vaikka olisi keksittykin, mutta luvut laitettu todennäköisiksi), niin tuo minun vastaus 0.0037 on kyllä liian iso, sillä todennäköisyys, että vie vähintään 5000 yritystä on tällöin
(1-0.0037)^5000 = 0.9e-9
eli erittäin pieni.
Arvolla p = 2e-05, se että vie korkeintaan 5000 yritystä olisi
1 - (1-2e-05)^5000 = 0.095
eli vähän järkevämpi.- Anonyymi
En tiedä simuloinko väärin. Tässä koodini:
from random import shuffle
tulos = [0]* 13
kertoja = 100000
for kerta in range(kertoja):
x = [i for i in range(52)]
shuffle(x)
y = x[0:13]
z = x[13:26]
A = []
B = []
for i in range(13):
A.append(y[i] % 13)
B.append(z[i] % 13)
yhteiset = set(A) & set(B)
tulos[len(yhteiset)] = 1
for i in range(13):
print(tulos[i]/kertoja)
print(summa) Anonyymi kirjoitti:
En tiedä simuloinko väärin. Tässä koodini:
from random import shuffle
tulos = [0]* 13
kertoja = 100000
for kerta in range(kertoja):
x = [i for i in range(52)]
shuffle(x)
y = x[0:13]
z = x[13:26]
A = []
B = []
for i in range(13):
A.append(y[i] % 13)
B.append(z[i] % 13)
yhteiset = set(A) & set(B)
tulos[len(yhteiset)] = 1
for i in range(13):
print(tulos[i]/kertoja)
print(summa)Hmmm.. Siinä taitaa käydä niin, että kun sä otat nuo yhteiset joukkona, niin se ei huomioi sitä kuinka monta A:sta poistuu (eli pinon kokoa). Minä muutin koodia näin (
ja nyt se antaa samanlaisen tuloksen kuin itselläni)
tulos = [0]* 14
.
.
.
#yhteiset = set(A) & set(B)
..for u in B:
....while u in A: A.remove(u)
..tulos[len(A)] = 1
.
.
Tai miksei jopa kirjoittaisi tuota A:n ja B:n täyttöä suoraan:
A = [u for u in y]
B = [u for u in z]
PS. Tuota että Pythonissa joukot voi &-operaattorilla leikata, ja näköjään myös |-operaattorilla yhdistää) en tiennytkään. Kätevä!minkkilaukku kirjoitti:
Hmmm.. Siinä taitaa käydä niin, että kun sä otat nuo yhteiset joukkona, niin se ei huomioi sitä kuinka monta A:sta poistuu (eli pinon kokoa). Minä muutin koodia näin (
ja nyt se antaa samanlaisen tuloksen kuin itselläni)
tulos = [0]* 14
.
.
.
#yhteiset = set(A) & set(B)
..for u in B:
....while u in A: A.remove(u)
..tulos[len(A)] = 1
.
.
Tai miksei jopa kirjoittaisi tuota A:n ja B:n täyttöä suoraan:
A = [u for u in y]
B = [u for u in z]
PS. Tuota että Pythonissa joukot voi &-operaattorilla leikata, ja näköjään myös |-operaattorilla yhdistää) en tiennytkään. Kätevä!Prosentit näköjään muuttui joksikin, (taisvat jäähä kiinni u:hun), kokeillaas uudestaan:
A = [u % 13 for u in y]
B = [u % 13 for u in z]
- Anonyymi
Tarinan mukaan vankilan johtaja sovelsi peliä elinkautisvankiin. Sai joka päivä pelata yhden pelin ja pääsi vapaaksi, jos sai kaikki kortit poistettua pöydältä. Ja tarinan mukaan pääsi vapaaksi 13 vuoden päästä eli noin 5000 pelin jälkeen. Oli onnekas, jos tn on tosiaan tuo 2*10^(-5).
Tässä hieman pohdelmiani:
Kun valitaan 13 korttia pöydälle ja ne jakautuvat pinoihin, niin kutsutaan näitten pinojen kokojen järjestettyä vektoria tämän valinnan tyypiksi.
On 39 erilaista tyyppiä (laskin Pythonilla: https://github.com/minkkilaukku/prisoners-solitaire/blob/master/prisoners.py ):
[4, 4, 4, 1], [4, 4, 3, 2], [4, 4, 3, 1, 1], ..., [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Löysin mielestäni kaavan sen laskemiseksi, kuinka monta pakan 13-kombinaatiota on tyyppiä (t1, t2,..., tr) tuolla tiedostossa on se kaava funktiona calcTypeOccurs(t, suits, vals). Se on tulo tyypin yli termistä
(vals-i)*binomial(suits, ti)
ja sitten vielä jaetaan koko tulo sillä kuinka monella tavalla tyypissä olevat samat luvut voivat keskenään permutoida, se on getTypeInnerPermuFactor(t).
Sitten pitäisi vielä laskea sellaiset luvut, että kun pakasta on poistettu kortteja tyypin t mukaisesti, niin kuinka monta 13-kombinaatiota jäljellä olevista on sellaisia, että niissä on ainakin 1 jokaista t:n korttia (mielestäni se voidaan WLOG olettaa että ne t:n kortit ovat 0, 1, 2,.., r). Tein jo sen bruteforcen, mutta mitenkäs se kaavan keksiminen. Tuo ensimmäisen valinnan laskuhan on sama kuin tämäkin, mutta siinä ei olla poistettu mitään vaan jokaista korttia on 4 (=suits) kappaletta, joten se oli siten yksinkertaisempi.""Tuo ensimmäisen valinnan laskuhan on sama kuin tämäkin, mutta...""
Tai siis, nythän lasketaan eri asiaa: sillä toisen valinnan tyypillä ei ole väliä vaan siinä pitää olla vähintään 1 jokaista jotain kiinitettyä lukua, joten ei se lasku ole sama, mutta jotain saman tyyppistä pohdintaa siinä pitää varmaan harjoittaa(?)Niin ja tämä on siis vain tuon X=0 tapauksen laskemista kohden tämä jälkimmäisen valinnan lasku. Sehän menee erittäin monimutkaiseksi se, että monta sitten lopulta jää.
Minä aloitan nyt pohdinnan uudesta kulmasta.
Kun se pöydän tyyppi on tullut, niin lähdetään yksi kerrallaan ottamaan pakasta niitä testauskortteja (nythän on helppo laskea tn. siirtyä toiseen tyyppiin ja siihen mitä pakassa on jäljellä (jos tulee tyhjä kortti, niin pöydän tyyppi ei muutu, mutta pakassa on yksi kortti vähemmän, voisiko se olla niin, että se ei riipu mikä kortti sieltä 'tyhjänä' heitetään pois vaikka tyyppi muuttuisikin sitten jatkossa eli siihen tulisi eri edustajat niille tyypin luvuille??
Silloinhan sen saisi melko helposti luultavasti dynaamisella ohjelmoinnilla laskettua. Pitäisi koittaa...Funktio
calculateProb(suits, vals, handLen, pickN)
näyttäisi toimivan, mutta ne jälkimmäiset luvut lasketaan yhä brute-forcena. Kokeilin pienillä arvoilla ja vertasin simuloituun arvoon."Toisten lukujen" laskemiseksi:
Olkoon M = {nj * j} multijoukko (alkiota j nj kappaletta, j=1..m). Sen k-kombinaatioiden lukumäärä saadaan polynomin
(1 z ..z^n1) * ... * (1 z ...z^nm)
termin z^k kertoimesta. Ja sellaisten kombinaatioiden, joissa alkioita j, j=1..p, on ainakin yksi saadaan, kun jätetään ykkönen pois näistä polynomeista tuossa yllä olevassa tulossa. (Tai yleisemmin: otetaan vain ne termit kuhunkin polynomiin mitkä lukumäärät tälle alkiolle kombinaatioon sallitaan).
Muistatteko sen lotto-tehtävän, tämähän on samanlainen! Mutta nyt tuloon tulee monen tyyppisiä termejä, riippuen millainen tyyppi pakasta on otettu pois. Mathematica osaisi varmaan tehokkaasti laskea nuo kertoimet. Löytyisiköhän Python-koodia mistä?
Vastaus siis saadaan, kun otetaan summa jokaisen tyypin yli (niitä oli ne 39) termeistä
P(pöydälle tulee tämä tyyppi t) * P(jäljellä olevasta pakasta (josta siis poistettu tyypin t mukaan) tulee sellainen 13-kombinaatio, että siinä on vähintään 1 jokaista tyypin korttia).
Nämä jälkimmäiset todennäköisyydethän voisi laskea jopa siten, että ajattelee pakkaa multijoukkona {(4-t1)*1, (4-t2)*2, ..., (4-tr)*r, (loput)*(r 1)}, eli emäfunktion viimeinen polynomi olisi (1 z ... z^loput). Osoittajaan kerroin siitä missä ykköset jätetty 1..r:stä pois ja nimittäjään siitä missä ne mukana.
Haa, tein Sage-koodin:
R.<z> = QQ['z']
vals = 5 #13
k = 7 #13
t = [3,2,1] #[3, 2, 2, 2, 1, 1, 1, 1]
njs = [4- (t[i] if i<len(t) else 0) for i in range(vals)]
g = 1 #the generating polynomial for suotuisat
gAll = 1 #for all
#it is the product
for i in range(len(njs)):
giCoeffs = [1]*(njs[i] 1)
gAll *= R(giCoeffs[:])
if i<len(t):
giCoeffs[0] = 0
g *= R(giCoeffs)
#print g
#print gAll
print "suotuisat"
print g[k]
print "kaikki"
print gAll[k]
Osoitteessa https://sagecell.sagemath.org/ voi suorittaa. Nyt kun jaksaisi vielä siirtää muut laskelmat tuohon ikkunaan, niin saisi ehkä vastauksen P(X=0):lle.Tein sen noin mutta antoi väärän tuloksen. Mutta nyt taidan ymmärtää mistä se johtuu:
Tuo antaa ne multijoukon kombinaatiot ihan oikein, mutta ongelma on siinä, että näiden todennäköisyydet tulla on erilaisia. Esim jos pakassa on 2 nollaa, 2 ykköstä ja 4 kakkosta, niin kombinaation '0,0,1' saaminen on pienempi kuin '0,0,2':n.
Korjaisikohan asian, jos mietittäisiinkin permutaatioita ja käytettäisiin eksponentiaalisia emäfunktioita?
Ei kyllä näyttäisi ihan suoraan vaan 1/k!:t polynomeihin polkaisemallakaan toimivan.
No nyt sain tuloksen
P(X=0) =
964444044208 / 262190765217675
= 0.00367840584853
Tämän näköisellä koodilla: https://github.com/minkkilaukku/prisoners-solitaire/blob/master/prisoners.pyKoodia optimoitu nyt erittäin merkittävästi: siinä kun lasketaan niitä pakasta toisessa vaiheessa tulevia kelpaavia tyyppejä, että monta kutakin sellaista on, niin voidaan rajoittaa ne niin, että sen vektorin summa on korkeintaan se kuinka monta valitaan toisessa vaiheessa (13 tässä perusversiossa). Ne generoidaan siten, että otetaan kaikki lukujen |t|..pickN ositukset ja permutoidaan nämä. Tähän on funktio generateMultipermus -- muuten 13:n pituisten permutaatioiden kanssa olisi ehkä tulla vähän ongelmia (vaikka eihän siellä ole kuin se yksi 13 pituinen, kaikki ykkösiä ja siitä ei sitten tule itseasiassa kuin 1!
minkkilaukku kirjoitti:
Koodia optimoitu nyt erittäin merkittävästi: siinä kun lasketaan niitä pakasta toisessa vaiheessa tulevia kelpaavia tyyppejä, että monta kutakin sellaista on, niin voidaan rajoittaa ne niin, että sen vektorin summa on korkeintaan se kuinka monta valitaan toisessa vaiheessa (13 tässä perusversiossa). Ne generoidaan siten, että otetaan kaikki lukujen |t|..pickN ositukset ja permutoidaan nämä. Tähän on funktio generateMultipermus -- muuten 13:n pituisten permutaatioiden kanssa olisi ehkä tulla vähän ongelmia (vaikka eihän siellä ole kuin se yksi 13 pituinen, kaikki ykkösiä ja siitä ei sitten tule itseasiassa kuin 1!
Jos pakassa olisi 16 korttia kutakin 4 maata, niin voitto-tn. olisi
1354983985597413560192/1457082583811094293369085 = 0.000929929436157
Se on kuitenkin nuo partitio-luvut, jotka tyyppien määrät ovat ja kasvavat eksponentiaalisesti, niin ei tällä menetelmällä kovin pitkälle pötkitä, tuokin vei jo taas 14 sekuntia.minkkilaukku kirjoitti:
Jos pakassa olisi 16 korttia kutakin 4 maata, niin voitto-tn. olisi
1354983985597413560192/1457082583811094293369085 = 0.000929929436157
Se on kuitenkin nuo partitio-luvut, jotka tyyppien määrät ovat ja kasvavat eksponentiaalisesti, niin ei tällä menetelmällä kovin pitkälle pötkitä, tuokin vei jo taas 14 sekuntia.Ai niin, ja tuo siis jos lätkittäisiin 16 kolmentoista asemesta myös pöydälle ja sen jälkeen nostettaisiin pakasta, eli 'joka kolmas', niinkuin se alunperin ilmaistiin.
Ne luvuthan (boardN ja pickN) siinä kasvattavat laskentaa. Jos olisi 50*4 korttia, ja boardN = pickN = 13, niin tulos on
1416074149056783184/17785457959223804854010008101 = 7.96197743293e-11
eikä laskenta vie kuin sekunnin.
No nyt toimii generoivat funktiotkin! Sinne piti laittaa binomikertoimet painottamaan. Koodi (Sagea): https://github.com/minkkilaukku/prisoners-solitaire/blob/master/prisonersSage.py
Tämä jaksaa isompiakin, esim
suits = 4
vals = 40
boardN = vals
pickN = 2*vals
p = calcWinProb(suits, vals, boardN, pickN)
= 2.734e 65 / 4.042e 66
= 0.0676372602897
Ketjusta on poistettu 1 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Hallituksen järjestämä spektaakkeli tuo vessanpyttykeissi
Että olisi kymmenien kansanedustajien kodeissa käyty ihan tuosta vaan, eikä kukaan kansanedustaja kerro niin käyneen, va3561438Sysmän "ilon päivä"
Ja taas palaa hirveä määrä verorahoja, ihan turhaan soopaan. Eikö nämä jotka kuntapolitiikassa valittavat ja tuhoaa vaan79987Timo Vornanen.
On siinäkin yksi täystampio. Eipä ihme, että persukannattajat sen eduskuntaan äänestikin.84905Uskon, että saataisiin kaikki selvitettyä
Mutta yhteys on jäissä, minä olen jäässä, enkä osaa tai uskalla enää lähestyä. Se vaan on niin. Naiselta Jos ei ole hyvä61833Riitastako pelastaja
Riitta jätti hakemuksen. Hyvä niin. On ainakin yksi mistä ottaa. Pertsa ei taida aikuistua koskaan ja Pekka hoiteli silt49728- 121705
Joka ilta mietin
sua❤️Mitä teet, missä meet? Kaipaatko yhtään? Yön tullen toivotan mielessäni sulle hyvää yötä ja aamuisin huomenet. Joka38692- 49658
- 50616
Tässä ovat Elämäni biisi -vieraat lauantai 3.10. - Yksi vieras on todellinen suomalaisten suosikki
Jos menisit Elämäni biisiin, mikä olisi elämäsi biisi ja miksi? Elämäni biisi tulee suorana lähetyksenä Tampereelta. K10568- 29564
Luottamus
Luotan vain siihen mitä tapahtuu IRL. Anonyymipalstan vihjailut eivät merkitse minulle mitään.95552- 45547
- 32531
Kadutko mies sitä miten reagoit?
..siihen sotkuun, jonka jälkeen mikään ei ole ollut kuin ennen. 🥺48525En voi kertoa meistä kenellekään
Minulla on ikävä sinua mies.. Oon yrittänyt taas unohtaa, mutta silti tulet mieleeni lähes päivittäin. Eihän meitä voi o33518Millaisen talvitakin haluaisit?
Talveen vielä aikaa, mutta talvitakit tulleet kauppoihin. Millainen olisi unelmiesi talvitakki? Itse tykkäisin jostain84495- 41492
- 80470
- 48459